package com.cheng.dataStructure.hashtable;

import java.util.Scanner;

/**
 * @User Administrator
 * @Classname HashTabDemo01
 * @Project Data-structure-and-algorithm
 * @Description 利用hash表实现下面问题：
 * 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的id时,要求查找到该员工的所有信息.
 * 要求：不使用数据库,速度越快越好，添加时，保证按照id从低到高插入
 * @Author wpcheng
 * @Create 2021-08-19-11:02
 * @Version 1.0
 */
public class HashTabDemo01 {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(7);
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("菜单选项：");
            System.out.println("add，添加员工");
            System.out.println("find，查找员工");
            System.out.println("list，查看所有员工");
            System.out.println("del，删除员工");
            System.out.println("exit，退出");

            key = scanner.next();

            switch (key) {
                case "add":
                    System.out.println("输入id:");
                    int id = scanner.nextInt();
                    System.out.println("输入姓名:");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "find":
                    System.out.println("输入id:");
                    int findId = scanner.nextInt();
                    hashTab.findEmpById(findId);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "del":
                    System.out.println("输入id:");
                    int delId = scanner.nextInt();
                    hashTab.deleteEmp(delId);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}

//创建哈希表
class HashTab {
    //定义数组，管理链表，哈希表本质就是一个数组
    private EmpLinkList[] empLinkListArray;
    private int size; //链表的数量

    //构造器初始化数组
    public HashTab(int size) {
        this.size = size;
        empLinkListArray = new EmpLinkList[size];
        //分别初始化每个链表
        for (int i = 0; i < size; i++) {
            empLinkListArray[i] = new EmpLinkList();
        }
    }

    //添加雇员
    public void add(Emp emp) {
        int empLinkListNo = hashFunction(emp.id);
        empLinkListArray[empLinkListNo].addEmp(emp);
    }

    //遍历所有链表
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkListArray[i].list(i);
        }
    }

    //根据id在hash表中查找员工
    public void findEmpById(int id) {
        //先确定要查找的id位于哪条链表中
        int empLinkListNo = hashFunction(id);
        //在具体的链表（empLinkListArray[empLinkListNo]）中进行查找
        Emp emp = empLinkListArray[empLinkListNo].findEmpById(id);
        if (emp != null) {
            System.out.printf("在第%d条链表中找到id为" + id + " 的员工", empLinkListNo);
        } else {
            System.out.println("在hash表中没有找到id为" + id + " 的员工");
        }
    }

    //根据员工id删除员工
    public void deleteEmp(int id) {
        int empLinkListNo = hashFunction(id);
        empLinkListArray[empLinkListNo].deleteEmp(id);
        System.out.println("删除成功");

    }


    //编写哈希（散列）函数，哈希函数指将哈希表中元素的关键键值（员工id）映射为元素存储位置（数组下标）的函数。
    // 通俗说明：哈希函数就是一个方法或者说函数关系，将员工id计算成对应哈希表中的存储位置，这样员工在添加时，才能确定添加到数组的那哪条链表中
    public int hashFunction(int id) { //取模法
        return id % size;
    }

}


//定义链表，链表里面存放员工节点
class EmpLinkList {
    //定义头结点,初始化为null
    private Emp head;

    /**
     * 添加员工节点的方法，每次添加节点都添加到链表最后吗
     *
     * @param emp
     */
    public void addEmp(Emp emp) {
        //如果添加的是第一个员工
        if (head == null) {
            head = emp;
            return;
        }
        //如果添加的不是第一个员工
        //定义辅助变量temp
        Emp temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;//temp后移
        }
        temp.next = emp;
    }

    //遍历链表员工节点信息
    public void list(int no) {
        if (head == null) {
            System.out.println("第" + no + " 链表为空");
            return;
        }
        System.out.print("第" + no + " 链表为：");
        Emp temp = head;
        while (true) {
            System.out.printf("=> id=%d name=%s\t", temp.id, temp.name);
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        System.out.println();

    }

    //根据id在链表中查找员工
    public Emp findEmpById(int id) {
        //如果当前链表为空
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        Emp temp = head;
        while (true) {
            if (temp.id == id) {
                break;
            }
            if (temp.next == null) {
                temp = null;
                break;
            }
            temp = temp.next;
        }
        return temp;
    }

    //根据员工id删除员工
    public void deleteEmp(int id) {
        if (head.id == id){
            head = null;
            return;
        }
        boolean flag = false;
        //定义辅助变量，指向被删除元素的前一个节点
        Emp temp = head.next;
        while (true) {
            //如果当前链表为空
            if (temp == null) {
                System.out.println("链表为空");
                break;
            }
            if (temp.id == id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp = temp.next;
        } else {
            System.out.println("未找到id为" + id + " 的员工");
        }
    }


}

//定义节点，每个节点表示一个员工
class Emp {
    public int id;
    public String name;
    public Emp next; //指向下一个节点

    public Emp(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}

